МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
ІКТА
Курсова робота
з курсу
«Моделювання паралельних обчислень»
Тема « Використання мереж Петрі при моделюванні паралельних обчислень»
ЛЬВІВ 2008
ЗМІСТ
1. Теоретичні відомості 3
2. Постановка та аналіз завдання 5
3. Загальна структура мережі Петрі на рівні функціональних блоків 7
4. Мережі Петрі, що реалізовують всі функціональні блоки з розгорнутим поясненням їх роботи 12
5. Результати тестування мережі 16
Висновок 17
Список використаної літератури 18
Теоретичні відомості
Мережі Петрі призначені для представлення координації асинхронних подій і застосовуються для описування взаємовідносин між паралельними процесами та їх синхронізацією.
Мережа Петрі – це орієнтований, дводольний граф з мітками (марками). Це визначення треба розуміти так (рис.1.1):
Кожна мережа Петрі є графом з двома різними групами вершин: вузли та переходи. Між вузлами та переходами можуть міститися орієнтовані ребра (дуги), але два вузли або два переходи не можуть з’єднуватися ребрами. Між кожною парою вузол/перехід може існувати максимально одне ребро від вузла до переходу (ребро входу) i максимально одне ребро від переходу до вузла (ребро виходу). Вузли можуть бути вільними або зайнятими міткою (маркованими); переходи не можуть бути маркованими. Вузли, що є стартовими пунктами одного ребра до одного переходу t, називаються далі вхідними вузлами переходу t. Вузли, що є кінцевими пунктами ребра від переходу t називаються вихідними вузлами переходу t.
На рис.1.2 показано просту мережу Петрі, що має один перехід, три ребра i три вузли, два з яких марковані i один не маркований. Кожен вузол зв’язаний з переходом за допомогою одного ребра.
За допомогою мереж Петрі можна моделювати такі якості як:
асинхронність,
конфліктнісь,
паралелізм.
Основні методи дослідження мереж Петрі:
Дерево досягальності,
Графічний,
Аналітичний,
За допомогою еквівалентних сумуючись.
Взагалі, мережі Петрі досліджують на такі властивосі:
Безпечність — досліджує виконання умови що кількість «фішок» в позиції не перевищує 1;
Обмеженість — досліджує виконання умови що кількість «фішок» в позиції не перевищує заданого числа,
Зберігальність — досліджує виконання умови що кількість «фішок» в мережі не змінюється,
Оберненість — для довільного досяжного стану досліджується існування послідовності виконань переходів яка повертає мережу в початковий стан),
Активність переходів — досліджує можливість виконання певних переходів та наявність тупиків — станів у яких переходи не дозволені та для яких неможливо досягти стану в якому ці переходи дозволені,
Досяжність маркування — досліджує існування послідовності виконань переходів при якій можна досягнути задане маркування,
Покриття — досліджує існування послідовності виконань переходів при якій можна досягнути маркування що покриває (є більшим) за задане маркування.
2. Постановка та аналіз завдання
Побудувати мережу Петрі, яка обраховує наступний вираз:
Задано цілі додатні числа . Знайти :
якщо – комплексне число, [a/b]– ціла частина від ділення.
Вершини вхідних даних містять цілі невід’ємні числа i можуть з’явитися лише один раз. У мережі мають бути помічені вершини “старт”, “фініш” та “помилка”.
Проаналізувавши вираз можна побачити, що в виразі присутні такі операції: множення двох чисел, піднесення чисел до степеня, додавання двох чисел, ділення, віднімання. Всі ці операції можна представити окремими блоками. Блоки множення двох чисел будуть також використовуватись у блоці піднесення до степеня.
Проаналізувавши вираз можна визначити спрощений його варіант:
Визначимо дійсну та уявну частини:
Re=
Im=
Також можна відзначити частини виразу, які можливо опрацювати паралельно:
Блок CountRe обчислює
На початку роботи виконується розмноження вхідних даних U1,U2 і V на блоки U1^2, U2^2 та V^2 свою...
